이번 포스트에서는 시간 복잡도와 공간 복잡도를 표현하는 일반적인 방법인 “빅오 표기법”을 알아본다.
시간 복잡도와 공간 복잡도에 대한 글은 이전글을 참고할 수 있다.
빅 오 표기법(big-O notation)
빅오 표기법이란?
알고리즘의 실행 시간을 이론적으로 측정한 지표.
알고리즘의 효율성을 나타내는 지표로 활용되며, 시간 복잡도, 공간 복잡도 등을 표현하는 일반적인 방법으로 사용된다.
두 복잡도를 나타내는 방법으로는 빅오(big-O), 빅 오메가(Ω), 빅 세타(Θ) 표기법 등이 존재한다. 이 방법들은 점근 표기법이다.
왜 빅 오 표기법일까?
빅 오 표기법은 알고리즘 실행 시간의 상한을 나타낸 표기법이다. 이 방법은 모든 경우의 수를 포함하며, 때문에 최악의 경우(=최악의 효율)를 나타내는데 사용한다. 모든 경우를 포함하기 때문에 알고리즘 실행 시간 계산에 사용된다.
빅 오메가 표기법은 하한을 표기한 방법이다. 가장 최적의 방법을 고려한 것이며, 데이터가 최적으로 주어지지 않으면 실현되기 어렵기 때문에 잘 사용하지 않는다.
빅 세타 표기법은 상한과 하한의 중간을 사용하며, 이 역시 빅 오 표기법을 사용하는것이 더 좋기 때문에 잘 사용하지 않는다.
빅 오 표기법의 사용
결과에 가장 많은 영향을 끼치는 하나의 항만 남긴다.
빅 오 표기법은 알고리즘이 입력 데이터 값(n)이 아주 큰 값으로 들어온다고 가정한다. 때문에 다음과 같은 표기가 가능하다.
1. 상수항 무시
n이 아주 큰 값으로 커지게 되면 상수항도 무시할 수 있다.
O(2n) => O(n)
2. 최고차항 이외의 항 무시
결과에 가장 영향을 많이 미치는 항 하나만 남기고 무시할 수 있다.
이 때, 가장 큰 영향을 미치는 항은 최고차항이며 이외의 항을 무시한다.
O(3n^3+2N+5) => O(n^3)
빅 오 표기법의 종류와 성능
종류
| f(n) | 예시 |
|---|---|
| 1 | stack의 push, pop |
| log n | 이진 탐색 |
| n | 트리 순회, for문 |
| n log n | 퀵소트, 머지소트, 힙정렬 |
| n^2 | 버블, 삽입, 선택 정렬 |
| n^3 | |
| 2^n | 피보나치 수열 |
-
O(1)
- 입력 데이터 양과 관계 없이 일정한 실행시간을 갖는다.
- 문제 해결 시 한 단계만 거친다.
- stack에서의 push, pop과 같은 실행.
-
O(log n)
- 입력 데이터 양이 많아져도 시간이 조금씩 늘어난다.
- 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형.
- 이진 탐색과 같은 실행
-
O(n)
- 데이터 양에 따라 시간이 정비례한다.
- for문을 통한 탐색.
-
O(n log n)
- 데이터 양이 n배 많아질 때 실행 시간은 n배 보다 조금 더 많아진다. (정비례 하지는 않는다.)
- 커다란 문제를 독립적인 작은 문제로 쪼개어 각가에 대해 독립적으로 해결하고, 다시 하나로 모으는 경우에 나타난다.
- 퀵소트(평균 수행 시간), 머지소트와 같은 실행
-
O(n^2)
- 데이터 양에 따라 걸리는 시간은 제곱에 비례.
- 효율이 좋지 못하며, 효율성을 따지는 문제에서는 사용을 지양한다.
- 이중루프 내에서 입력 데이터를 처리하는 경우 발생한다.
- 버블 소트, 삽입 정렬, 선택 정렬 및 퀵소트(최악의 경우)
성능
빠름 O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) 느림
버블, 퀵, 합병 정렬 시간복잡도
자주 사용되는 정렬의 시간복잡도와 그 이유를 알아본다.
-
버블 정렬
- O(n^2)
- 인접한 두 개의 원소를 비교하여 자리를 계속 교환하는 방식
- 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬
- 2중 for문을 사용한다.
-
퀵 정렬
- 평균 실행 시간 : O(n log n)
- 최악 실행 시간 : O(n^2) => 정렬된 리스트
- 피봇보다 큰 값은 오른쪽, 작은 값은 왼쪽에 위치시켜 피봇을 두 집합의 가운데에 위치시킨다.
- 리스트를 비균등하게 분할
- 순환 호출의 깊이 : log n
- 비교해야 하는 횟수 : n
- 평균 실행 시간 : O(n log n)
- 피봇을 정렬해야 할 리스트의 첫번째 값으로 선택해서 정렬한다. 때문에 이미 정렬된 리스트에 대해서는 최악의 실행시간이 나올 수 있다.
- 순환 호출의 깊이 : n
- 비교해야 하는 횟수 : n
- 최악의 실행 시간 : O(n^2)
-
합병 정렬(merge sort)
- O(n log n)
- 하나의 리스트를 두 개의 균등한 크기로 분할하고, 분할된 리스트를 정렬한 다음, 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법.
- 분할 및 결합하는 방법. 순환호출의 깊이 : log n
- 비교해야 하는 횟수 : n
- 평균 실행 시간 : O(n log n)